/*
 * @lc app=leetcode.cn id=62 lang=java
 *
 * [62] 不同路径
 */

// @lc code=start
class Solution {
    //动态规划，动态规划转移方程： f(i,j)=f(i−1,j)+f(i,j−1)
    // 可将所有的f(0,j) f(i,0)设为1，即边界条件
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for(int i=0 ;i<m ;i++){
            f[i][0] = 1;
        }
        for(int j=0 ;j<n ;j++){
            f[0][j] = 1;
        }
        for(int i = 1 ;i<m ;i++){
            for(int j=1 ; j<n ;j++){
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }

    //其实这题还可以用组合数来解
    // 等于从 m+n-2次移动中选择 m−1次向下移动的方案数，即组合数
    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }

}
// @lc code=end

